package edu.bupt.c1array;

public class T13TrappingRainWater {
    public int trap(int[] height) {
        if(height.length < 3) return 0;

        //1-求出单边最小的值；
        int[] left = new int[height.length];
        int max = 0;
        for (int i=0;i<height.length;i++){
            left[i] = max;
            if (height[i] > max){
                max = height[i];
            }
        }

        //2-求右侧最大的值
        int[] right = new int[height.length];
        int maxright = 0;
        for (int i=height.length-1;i>=0;i--){
            right[i] = maxright;
            if (height[i] > maxright){
                maxright = height[i];
            }
        }

        // 3-求每块的雨水之和
        int sum = 0;
        for(int i=1;i<height.length-1;i++){
            int temp = Math.min(left[i], right[i]);
            if (height[i] < temp){
                sum = sum + temp - height[i];
            }

        }
        return sum;
    }
}
